package Leetcode.树;

import java.util.*;

/**
 * @ClassName TrNode
 * @since: 2023/8/18 17:12
 * @auth: kirito
 * @description:
 **/
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode() {}
    public TreeNode(int val) { this.val = val; }
    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    /**
     * 数组 构建成一棵树
     * @param arr   数组
     * @return  根节点
     */
    public static TreeNode arrayToTree(Integer[] arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }

        TreeNode root = new TreeNode(arr[0]);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        int i = 1;
        while (!queue.isEmpty() && i < arr.length) {
            TreeNode node = queue.poll();
            if (arr[i] != null) {
                node.left = new TreeNode(arr[i]);
                queue.add(node.left);
            }
            i++;
            if (i < arr.length && arr[i] != null) {
                node.right = new TreeNode(arr[i]);
                queue.add(node.right);
            }
            i++;
        }

        return root;
    }

    /**
     * 最大深度
     * @param root
     * @return
     */
    public static int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int leftHeight = maxDepth(root.left);
            int rightHeight = maxDepth(root.right);
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
    /**
     * 层序遍历
     */
    public List<List<Integer>> levelOrder(TreeNode root) {

        List<List<Integer>> list = new ArrayList<>();
        Queue<TreeNode> que = new LinkedList<>();
        if (root == null) {
            return list;
        }
        que.add(root);
        while (!que.isEmpty()) {
            int size = que.size();
            List<Integer> res = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode poll = que.poll();
                res.add(poll.val);
                if (poll.left != null) {
                    que.add(poll.left);
                }
                if (poll.right != null) {
                    que.add(poll.right);
                }
            }
            list.add(res);
        }
        return list;
    }

    /**
     * 中序遍历 非递归
     * @param root
     */
    public static  List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode currentNode = root;

        while (currentNode != null || !stack.isEmpty()) {
            while (currentNode != null) {
                stack.push(currentNode);
                currentNode = currentNode.left;
            }

            currentNode = stack.pop();
            ans.add(currentNode.val);
            currentNode = currentNode.right;
        }
        return ans;
    }
    /**
     * 前序遍历
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(node.val);
            // 先右后左，保证左子树先遍历
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }

        return result;
    }

    /**
     * 后序遍历
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode lastVisited = null;
        TreeNode current = root;

        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            current = stack.peek();
            // 如果右子树不存在或已被访问，则访问当前节点
            if (current.right == null || current.right == lastVisited) {
                result.add(current.val);
                lastVisited = current;
                stack.pop();
                current = null; // 继续处理栈中的下一个节点
            } else {
                current = current.right;
            }
        }

        return result;
    }


    /**
     * 给你两棵二叉树 root 和 subRoot 。
     * 检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。
     * 如果存在，返回 true ；否则，返回 false 。
     * @param root
     * @param subRoot
     * @return
     */
    public static boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null ) {
            return false;
        }
        return isSameTree(root, subRoot)
            ||  isSubtree(root.left, subRoot)
            ||  isSubtree(root.right, subRoot);
    }

    /**
     * 两棵树是否是相同的树
     * @param p 节点1
     * @param q 节点2
     * @return  true false
     */
    private static boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null || q == null) {
            return p == q; // 必须都是 null
        }
        return p.val == q.val
            &&  isSameTree(p.left, q.left)
            &&  isSameTree(p.right, q.right);
    }

    /**
     * 根据前 中序还原二叉树
     */
    public TreeNode buildTree_pre_inorder(int[] preorder, int[] inorder) {
        //记录每个节点值对应在中序遍历种的索引
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        //root为先序的第一个节点 0开始
        return recur(preorder, map, 0, 0, inorder.length - 1);
    }

    private TreeNode recur(int[] preorder, HashMap<Integer, Integer> map, int root, int left, int right) {
        if (left > right) {
            return null;
        }
        // 建立根节点
        TreeNode node = new TreeNode(preorder[root]);
        // 获取根节点在中序中的索引，i-1就是right左子树的右边界 i+1就是右子树的左边界
        int i = map.get(preorder[root]);
        //左子树的根是当前节点root+1，对应的是先序中的索引
        node.left = recur(preorder, map, root + 1, left, i - 1);
        //i - left + root + 1含义为 根节点索引 + 左子树长度 + 1
        node.right = recur(preorder, map, root + i - left + 1, i + 1, right);
        return node;
    }

    /**
     *  后 中序还原二叉树
     */
    public TreeNode buildTree_post_inorder(int[] inorder, int[] postorder) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return buildTreeRecur(inorder, postorder, map, 0, inorder.length - 1, 0, postorder.length - 1);
    }
    /**
     *
     * @param inorder   中序遍历数组
     * @param postorder 后序遍历数组
     * @param map       一个HashMap，存储了中序遍历中每个值对应的索引，便于快速查找根节点位置
     * @param inStart   当前子树在中序遍历数组中的起始索引
     * @param inEnd     当前子树在中序遍历数组中的结束索引
     * @param postStart 当前子树在后序遍历数组中的起始索引
     * @param postEnd   当前子树在后序遍历数组中的结束索引
     * @return          构建好的子树的根节点
     */
    private TreeNode buildTreeRecur(int[] inorder, int[] postorder, HashMap<Integer, Integer> map,
                                    int inStart, int inEnd, int postStart, int postEnd) {
        if (inStart > inEnd || postStart > postEnd) {
            return null;
        }
        // 后序遍历的最后一个元素是根节点
        TreeNode root = new TreeNode(postorder[postEnd]);
        // 获取根节点在中序遍历中的索引
        int inRootIndex = map.get(postorder[postEnd]);
        // 左子树的长度
        int leftTreeSize = inRootIndex - inStart;

        // 构建左子树，左子树的根节点是后序遍历中的postStart + leftTreeSize
        root.left = buildTreeRecur(inorder, postorder, map,
                inStart, inRootIndex - 1, postStart, postStart + leftTreeSize - 1);
        // 构建右子树，右子树的根节点是后序遍历中的postStart + leftTreeSize
        root.right = buildTreeRecur(inorder, postorder, map,
                inRootIndex + 1, inEnd, postStart + leftTreeSize, postEnd - 1);

        return root;
    }

    /**
     * 验证给定的数组是否可以表示一个二叉搜索树的后序遍历序列。
     *
     * @param postorder 后序遍历的数组
     * @return 如果数组可以表示一个二叉搜索树的后序遍历序列，则返回true；否则返回false
     */
    public boolean verifyTreeOrder(int[] postorder) {
        // 从数组的开始和结束索引开始递归验证
        return recur(postorder, 0, postorder.length - 1);
    }

    /**
     * 递归验证子数组是否可以表示一个二叉搜索树的后序遍历序列。
     *
     * @param postorder 后序遍历的数组
     * @param i 子数组的起始索引
     * @param j 子数组的结束索引（也是子树的根节点）
     * @return 如果子数组可以表示一个二叉搜索树的后序遍历序列，则返回true；否则返回false
     */
    boolean recur(int[] postorder, int i, int j) {
        // 基本情况：如果子数组为空或者只包含一个元素，则它自然是一个二叉搜索树的后序遍历序列
        if(i >= j){
            return true;
        }

        // 初始化指针p，用来遍历子数组，找到第一个大于根节点的元素，这标志着左子树的结束和右子树的开始
        int p = i;
        while(postorder[p] < postorder[j]) {
            p++;
        }

        // m 是左子树的最后一个元素，也是右子树的第一个元素
        int m = p;

        // 继续遍历，确保右子树的所有元素都大于根节点
        while(postorder[p] > postorder[j]) {
            p++;
        }

        // 如果p等于j，说明右子树的所有元素都大于根节点，递归验证左子树和右子树
        return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
    }

    /**
     * 验证给定的数组是否可以表示一个二叉搜索树的后序遍历序列。
     * 栈实现
     */
    public boolean verifyTreeOrder_stack(int[] postorder) {
        // 使用栈来验证后序遍历序列是否可以表示一个二叉搜索树
        Stack<Integer> stack = new Stack<>();
        // 初始化root为最大整数值，确保第一个元素能够入栈
        int root = Integer.MAX_VALUE;

        // 从后序遍历的最后一个元素开始向前遍历
        for (int i = postorder.length - 1; i >= 0; i--) {
            // 如果当前元素大于根节点，则不是有效的二叉搜索树后序遍历序列
            if (postorder[i] > root) {
                return false;
            }

            // 当栈不为空且栈顶元素大于当前元素时，更新root为栈顶元素，并弹出栈顶元素
            // 这模拟了从右子树回到根节点的过程
            while (!stack.isEmpty() && stack.peek() > postorder[i]) {
                root = stack.pop();
            }

            // 当前元素入栈，模拟构建二叉搜索树的过程
            stack.add(postorder[i]);
        }

        // 如果所有元素都能按照二叉搜索树的规则入栈，则返回true
        return true;
    }

    /**
     * 二叉排序树从大到小输出不小于x的值
     */
    public void reverseInOrder(TreeNode root, int x) {
        if (root != null) {
            // 先访问右子树，因为我们需要从大到小的顺序
            reverseInOrder(root.right, x);

            // 如果当前节点的值不小于x，则输出
            if (root.val >= x) {
                System.out.println(root.val);
            }

            // 然后访问左子树
            reverseInOrder(root.left, x);
        }
    }
    /**
     * 二叉排序树从大到小输出不小于x的值    非递归
     */
    public void reverseInOrderIterative(TreeNode root, int x) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;

        // 开始遍历二叉树
        while (current != null || !stack.isEmpty()) {
            // 先将右子树的所有节点压入栈中
            while (current != null) {
                stack.push(current);
                current = current.right;
            }

            // 出栈，访问节点
            current = stack.pop();

            // 如果当前节点的值不小于x，则输出
            if (current.val >= x) {
                System.out.println(current.val);
            }

            // 然后转向左子树
            current = current.left;
        }
    }

    /**
     * 自底向上判断是否是平衡树；
     */
    public boolean isBalanced(TreeNode root) {
        return height(root) >= 0;
    }
    public int height(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftHeight = height(root.left)+1;
        int rightHeight = height(root.right)+1;
        if(leftHeight == 0 || rightHeight == 0 || Math.abs(leftHeight - rightHeight) > 1){
            return -1;
        }else{
            return Math.max(leftHeight, rightHeight);
        }
    }

    /**
     * 二叉树的完全性检验
     */
    public boolean isCompleteTree(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        //是否已经出想过空节点
        boolean reachedEnd = false;
        //这里为什么不用que的size大小循环作为条件判断呢？
        //因为只有一层不符合，就会false  所以不需要用size条件循环
        while(!q.isEmpty()){
            TreeNode cur = q.poll();
            //若已经出现过空节点，那么该层后边不应该出现节点，否则返回false
            if(reachedEnd && cur != null){
                return false;
            }
            if(cur == null){
                reachedEnd = true;
                continue;
            }
            q.offer(cur.left);
            q.offer(cur.right);
        }
        return true;
    }
    public int[] finalPrices(int[] prices) {
        int n = prices.length;
        int[] ans = new int[n];
        Deque<Integer> stack = new ArrayDeque<Integer>();
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() > prices[i]) {
                stack.pop();
            }
            ans[i] = stack.isEmpty() ? prices[i] : prices[i] - stack.peek();
            stack.push(prices[i]);
        }
        return ans;
    }


    public static void main(String[] args) {
        TreeNode test = new TreeNode();
//        Integer[] arr1 = {1,2,3,4,5,null,7};
//        TreeNode tree_1 = arrayToTree(arr1);
//        System.out.println(test.isCompleteTree(tree_1));
    }
}